package leetcode.editor.cn.dsa15_stackAndGA;
//给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1
//的一个排列。 
// 字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序
//）。 
//
// 示例 1： 
// 输入：s1 = "abc", s2 = "xya"
// 输出：true
// 解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。
//
// 示例 2： 
// 输入：s1 = "abe", s2 = "acd"
// 输出：false
// 解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，s2="acd" 的所有排列包括："a
//cd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排
//列。
//
// 示例 3： 
// 输入：s1 = "leetcodee", s2 = "interview"
// 输出：true
//
// 提示： 
// s1.length == n
// s2.length == n 
// 1 <= n <= 10^5 
// 所有字符串都只包含小写英文字母。 
// 
// Related Topics 贪心算法 字符串 
// 👍 12 👎 0

public class CheckIfAStringCanBreakAnotherString1433_2 {
    public static void main(String[] args) {
        Solution solution = new CheckIfAStringCanBreakAnotherString1433_2().new Solution();
        System.out.println(solution.checkIfCanBreak("fqh", "ayg")); //false
        System.out.println(solution.checkIfCanBreak("abe", "acd")); //false
        System.out.println(solution.checkIfCanBreak("leetcodee", "interview")); //true
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 最优解：
         * 上一种解法是比较索引，因为索引顺序代表了每个字母的字典序，
         * 但是每个字符都需要比较一次，所以最多比较次数为n次。
         * 最优解思路：
         * 其实完全可以按字母的总个数比较，同一个位置总个数大的肯定字典序小，
         * 因为总长度一样。这意味着当前个数少的元素必然可以替换个数多的元素
         * 也就是说s1能够打破s2的条件是：从a-z除了出现的最后一个字母个数，
         * s1其他每个字母的总个数总是 <= s2其他每个字母的总个数
         * 例如：aaaaabb 与 aabbcc
         * @param s1
         * @param s2
         * @return
         */
        public boolean checkIfCanBreak(String s1, String s2) {
            // 使用数组模拟哈希表，分别保存s1、s2字符串中字母出现的个数
            // 数组本身的索引值 [0-25] 就代表了字母 [a-z] 的字典顺序
            char[] arr1 = countStr(s1);
            char[] arr2 = countStr(s2);
            // check为1代表使用s2打破s1，为-1代表使用s1打破s2
            int check = 0;
            int sum1 = 0, sum2 = 0; // 代表当前字母的总个数
            for (int i = 0; i < 26; i++) {
                sum1 += arr1[i];
                sum2 += arr2[i];
                if (check == 0) { // 还未比较出结果
                    if (sum1 > sum2) { // 总个数大的字典序小
                        check = 1;
                    } else if (sum1 < sum2) {
                        check = -1;
                    }
                } else { // 已经确定用谁打破谁
                    if (check == 1 && sum1 >= sum2
                            || check == -1 && sum1 <= sum2) {
                    } else {
                        return false;
                    }
                }
            }
            return true;
        }
        char[] countStr(String s) {
            char[] res = new char[26];
            for (char c : s.toCharArray()) {
                res[c - 'a']++;
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}